Rapid advances in computing and communication technologies have fueled an explosive growth in the multimedia industry. The realization of multimedia services such as multimedia messaging, online news, interactive television, and video on demand requires the development of large scale servers, continuous media ("CM") servers, that are capable of transmitting CM clips, generally stored on disks to thousands of users. A CM clip is generally a sequence of frames of audio, video or some multimedia combination, whose transmission should be without delays between frames. For example, a movie is a CM clip since it would be not desirable to view the movie if there were delays between frames. This is not to suggest, however, that a delay inserted purposefully such as to create a pause while viewing the movie, will render the movie a non CM clip.
To be effective a CM server must be designed to guarantee that each CM clip stored on the server can be retrieved and transmitted at a prescribed transfer rate which depends on the compression technique used to store the clip and the required display rate, e.g., 30 frames per second. One factor that can prevent the CM server from satisfying the transfer rate is disk failure. In other words, the CM server may be physically blocked from accessing the CM clip from the storage medium.
To illustrate, consider that a single one hundred minute MPEG-1 video clip requires approximately 1.25 GB of disk space. With commercially available disks having between two to nine gigabytes of storage capacity, a CM server will require access to many disks in order to store hundreds of clips. Considering that a single disk has a mean time failure of approximately three hundred thousand hours, the mean time failure of a server with two hundred disks is approximately fifteen hundred hours, or sixty days.
A number of schemes have been proposed for ensuring the availability of data on failed disks. Many of these schemes employ data redundancy. Examples include S. Berson, et al., "Fault Tolerant Design of Multimedia Servers," in Proceedings of SIGMOD Conference, pp. 364-375 (1995); D. Bitton and J. Gray, "Disk Shadowing," in Proceedings of the 14th Conference on Very Large Databases, pp. 331-338 (1988); P. M. Chen, et al., "RAID: High Performance, Reliable Secondary Storage," submitted to ACM Computing Surveys (1994); G. Gibson and D. Patterson, "Designing Disk Arrays for High Data Reliability," Journal of Parallel and Distributed Computing, pp. 4-27 (January 1993); Antoine Mourad, "Reliable Disk Striping in Video-On-Demand Servers," Proceedings of the Int'l Conference on Distributed Multimedia Systems and Application (August 1995); D. Patterson, et al., "A Case for Redundant Array of Inexpensive Disks (RAID)," in Proceedings of ACM SIGMOD '88 pp. 109-116 (June 1988); F. A. Tobagi, et al., "Streaming RAID--A Disk Array Management System for Video Files," in Proceedings of ACM Multimedia '93 pp. 393-400 (1993); and H. M. Vin, et al., "Efficient Failure Recovery in Multi-Disk Multimedia Servers," in Proceedings of the Twenty-Fifth Fault Tolerant Computing Symposium (June 1995), all of which are hereby incorporated by reference as if fully set forth herein.
Many of these techniques assume a RAID architecture in which fault tolerance is achieved either by mirroring, or by parity encoding. Mirroring techniques achieve fault tolerance by replicating data on separate disks and thus encounter a 100% storage overhead. Parity encoding, on the other hand, stores a single parity block with parity information for a group of data blocks, thereby reducing the storage space overhead. Typically, for a group of data blocks residing on different disks, a parity block containing parity information for those data blocks is stored on a separate disk. In the event a disk containing a data block fails, the lost data block is reconstructed from the remaining data blocks in its parity group and their associated parity block.
Most of the experimental, analytical, and simulation studies for RAID based disk arrays assume a conventional workload in which reads and writes from and to a disk, access small amounts of data are independent of each other, aperiodic, and do not impose any real time requirements. In contrast, access to CM data is sequential, periodic, and imposes real time constraints. Schemes that exploit the inherent characteristics of CM data for data placement and recovery, and that enable CM data to be retrieved at a guaranteed rate despite disk failures were proposed in Antoine Mourad, "Reliable Disk Striping in Video-On-Demand Servers," F. A. Tobagi, et al., "Streaming RAID--A Disk Array Management System for Video Files," S. Berson, et al., "Fault Tolerant Design-of-Multimedia Servers," and H. M. Vin, et al., "Efficient Failure Recovery in Multi-Disk Multimedia Servers," supra.
In "Reliable Disk Striping in Video-On-Demand Servers" mirror blocks of data blocks on one disk are distributed among the other disks accessible by the server. This scheme is plagued with a 100% storage overhead since every data block is replicated. In "Streaming RAID--A Disk Array Management System for Video Files," parity encoding techniques are used to group disks into clusters of p disks, each cluster comprising one parity disk and p-1 data disks. A set of p-1 data blocks, one block per data disk in a cluster, and its parity block stored on the parity disk in the cluster, form a parity group. The granularity of a read request is an entire parity group. As a result, the parity block is always available to reconstruct lost data in case a data disk fails. The streaming RAID scheme has high buffer requirements since it retrieves an entire parity group in every access.
To reduce buffer space overhead for environments in which a lower level of fault tolerance is acceptable, a non-clustered scheme was proposed in "Fault Tolerant Design of Multimedia Servers," where disks are organized in clusters comprising a single parity disk. In the event of a disk failure, entire parity groups are read, but only for parity groups containing the faulty disk. With this scheme, however, blocks for certain clips may be lost during the transition from retrieving individual data blocks to retrieving entire parity groups for a failed cluster. As a result, a viewer of the CM clip may encounter discontinuities in the playback.
Another scheme proposed in "Fault Tolerant Design of Multimedia Servers" eliminates parity disks and stores parity blocks from a first cluster in an adjacent second cluster. In the event of a disk failure within the first cluster, the parity blocks are retrieved from the adjacent second cluster. The data blocks that could not be retrieved from the adjacent cluster due to the time spent retrieving the additional parity blocks are treated as lost, and are reconstructed from parity blocks retrieved from the next adjacent cluster. The advantage of this scheme is that disk bandwidth is utilized effectively during normal operation. However, in the event of a disk failure, retrieval of parity blocks may propagate through every cluster resulting in an increase in buffer requirements, and possibly lost clips. Moreover, if bandwidth is not available on a particular disk containing parity blocks to be retrieved, one or more requests may have to be terminated.